package problem494;

//494.目标和
//https://leetcode.cn/problems/target-sum/

// class Solution {
//     public int findTargetSumWays(int[] nums, int target) {
//         int n = nums.length;
//         int sum = 0;
//         for(int i = 0; i<n; i++) {
//             sum += nums[i];
//         }
//         int m = (sum + target)/2;
//         if(m < 0 || (sum + target)%2!=0) return 0;
//         int[][] dp = new int[n+1][m+1];
//         for(int i = 0; i<=n; i++) {
//             dp[i][0] = 1;
//         }
//         for(int i = 1; i<=n; i++) {
//             for(int j = 0; j<=m; j++) {
//                 dp[i][j] = dp[i-1][j]; //不选
//                 if(j-nums[i-1] >= 0) dp[i][j] += dp[i-1][j-nums[i-1]];
//             }
//         }

//         return dp[n][m];
//     }
// }

/*
sum = 5, target = 3;
a+b = sum
a-b = target
a = (sum+target)/2;
a:添加'+'的数
b:添加'-'的数
dp[i][j]:从前i个数中, 选出和为j, 总共有多少种选法
*/


//空间优化

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i<n; i++) {
            sum += nums[i];
        }
        int m = (sum + target)/2;
        if(m < 0 || (sum + target)%2!=0) return 0;
        int[] dp = new int[m+1];
        dp[0] = 1;

        for(int i = 1; i<=n; i++) {
            for(int j = m; j>=nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }

        return dp[m];
    }
}